def longest_increasing_subsequence(A):
    """
    A subsequence is a sequence that can be derived from an array by deleting 
    some or no elements without changing the order of the remaining elements. 
    For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

    E.g. If A=[4,1,7,3,10,2,5,9], then the longest subsequence is S=[1,3,5,9] or S=[1,2,5,9]
    """

    subsequence_lengths = [1] * (len(A))
    for i in range(len(A) - 1, -1, -1):
        for j in range(i + 1, len(A)):
            if A[j] > A[i]:
                subsequence_lengths[i] = max(
                    subsequence_lengths[i], 1 + subsequence_lengths[j]
                )
    return max(subsequence_lengths)


A = [4, 1, 7, 3, 10, 2, 5, 9]
print(longest_increasing_subsequence(A))